package datastrucure.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Fizz Pu
 * @Date 2021/4/16 下午5:24
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

public final class TrieTree {

    static class Node{
        // 字符
        private char ch;
        // key : 下一个字符 value: 下一个字符的引用
        private Map<Character, Node> next;
        // 是否是后缀
        private boolean isEnd;

        public Node(char ch){
            this.ch = ch;
        }

        public Node(){

        }
    }

    private Node root = new Node();

    /** Initialize your data structure here. */
    public TrieTree() {

    }

    /** Inserts a word into the trie. */
    // 遍历字符串, 通过map寻找下一个节点, 如果map为空则创建节点, 否则遍历下一个节点
    // 遍历结束后, 将isEnd置为空
    public void insert(String word) {
        if(word == null){
            return;
        }

        int len = word.length();
        Node current = root;
        Node nextNode;

        for(int i = 0; i < len; i++){
            char key = word.charAt(i);
            Map<Character, Node> map = (current.next == null) ? new HashMap<>() : current.next;
            current.next = map;
            if((nextNode = map.get(key))== null){
                nextNode = new Node(key);
                map.put(key, nextNode);
            }
            current = nextNode;
        }

        current.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word == null){
            throw new IllegalArgumentException();
        }

        int len = word.length();
        Node current = root;
        Node nextNode;
        char key;
        int index;
        for(index = 0; index < len; index++){
            if(current == null){
                return false;
            }

            Map<Character, Node> map = current.next;
            key = word.charAt(index);

            // 1. 未到达叶子节点, 退出后:index < len
            // 2. 到达叶子节点, 如果字符串未遍历完毕, 退出后:index < len
            // 3. 到达叶子节点, 如果字符串遍历完毕, 退出后:index == len
            if(map == null){
                break;
            }

            if((nextNode = map.get(key)) == null){ // 搜索不到
                return false;
            }
            current = nextNode;
        }
        return current.isEnd && index == len;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if(prefix == null){
            throw new IllegalArgumentException();
        }

        int len = prefix.length();
        Node current = root;
        Node nextNode;
        char key;
        int index;
        for(index = 0; index < len; index++){
            if(current == null){
                return true;
            }

            Map<Character, Node> map = current.next;
            key = prefix.charAt(index);

            if(map == null){
                break;
            }

            if((nextNode = map.get(key)) == null){
                return false;
            }
            current = nextNode;
        }
        return index == len;
    }

    // 删除字符串
    public void deleteString(String str){
        //todo
    }

    @Override
    public String toString() {
        return "TrieTree{" +
                "root=" + root +
                '}';
    }

    public static void main(String[] args) {
        TrieTree trie = new TrieTree();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
        trie.insert("我是你爸爸");
        System.out.println(trie.startsWith("我是"));
    }
}
